package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import com.gitee.feizns.explore.data_structure.union_find.UnionFind;

/**
 * 684. 冗余连接
 * @author feizns
 * @since 2020/3/11
 */
public class FindRedundantConnection {

    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind(edges.length);
        for (int[] edge : edges) {
            if ( uf.isConnected(edge[0], edge[1]) )
                return edge;
            uf.union(edge[0], edge[1]);
        }
        return null;
    }

    static class UnionFind {
        private int[] parents;
        private int[] ranks;
        public UnionFind(int size) {
            parents = new int[size];
            ranks = new int[size];
            for (int i = 0; i < size; i++) {
                parents[i] = i;
            }
        }

        public void union(int p, int q) {
            int pr = find(p);
            int qr = find(q);
            if ( pr != qr ) {
                if ( ranks[pr] < ranks[qr] )
                    parents[pr] = qr;
                else if ( ranks[pr] > ranks[qr] )
                    parents[qr] = pr;
                else {
                    parents[pr] = qr;
                    ranks[qr]++;
                }
            }
        }

        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }

        public int find(int p) {
            while ( p != parents[p] ) {
                parents[p] = parents[parents[p]];
                p = parents[p];
            }
            return p;
        }
    }

}
